Operational Transformation

分散環境で複数のユーザーが同時に行った操作を、互いの操作を考慮して変換・調整することで競合を解決するアルゴリズム。Google Docsなどが採用している。

基本的な仕組み

複数ユーザーの操作が異なる順序でサーバーに到達した場合、後から到達した操作を「先に適用された操作を踏まえて変換」してから適用する。

User Aの操作: insert(5, " World")   → "Hello World"
User Bの操作: replace(0, 4, "Hi")  → "Hi"

同時に発生した場合:
→ サーバーがUser Aの操作を変換
→ insert(2, " World") として適用
→ 最終結果: "Hi World"

特徴

• 中央サーバーが必要: すべての操作変換をサーバーで行う
• 変換ロジックが複雑: 操作の種類（挿入・削除・置換）の組み合わせに応じた変換ロジックが必要
• 実績がある: Google Docs、Microsoft Office Online等で長年使われてきた

CRDTとの比較

CRDT（Conflict-free Replicated Data Type）は、サーバーレスでも競合が起きないことを数学的に保証するアプローチで、OTの課題を解決するために考案された。

関連

• CRDT
• 協調編集
• 分散システム